//官方称呼解法为二分查找



//使用两次二分法就可以解决，第一次是为了找数组中最大的那一个数，第二次是为了找到目标值

/* var search = function(arr, target) {
    let i = 0
    while(arr[i]){
        if(arr[i] == target){
            return i
        }
    }
    return -1;
}; */
var search = function (arr,target){
    let len = arr.length
    let left = 0;
    let right = len-1
    //去掉最右边和最左边重复的地方
    while (right > 0 && arr[0] == arr[right]) right--;
    while(right>left){
        let mid = Math.floor((left+right+1)/2)
        if(arr[mid]>=arr[left]){
            left = mid
        }else{
            right = mid - 1
        }
    }
    if(arr[0] > target){
        left +=1;
        right = len-1;
    }else{
        left = 0
    }
    while(right>left){
        let mid = Math.floor(((left+right+1)/2))
        if(arr[mid]>=target){
            right = mid
        }else{
            left = mid+1
        }
    }
    return arr[right] == target ? right : -1
}
